package 数据结构OJ;

/**
 * @author shy_black
 * @date 2019/6/25 11:04
 * @Description:
 * 题目描述
 * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
 *
 * 解法1
 * 一开始尝试解这道题的时候其实有些不知道怎么下手，花了很长时间。后来才发现可以利用递归的思想，将n的值不断放小到某个可以直接知道结果的值。虽然直接实现递归的算法可能效率不高，但在找到题目的递归解法后，再在递归算法的基础上做优化，就可以得到一个满意的答案。
 * 回到本题，用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，假设有F(n)中方法
 * 先用一个2*1的小矩形，竖着覆盖大矩形，如下图所示。则还剩下2*(n-1)的大矩形需要覆盖，即有F(n-1)种方法
 *
 *
 * 如果先用一个2*1的小矩形，横着覆盖大矩形，如下图所示。则底部的红色区域也只能用一个2*1的小矩形横着覆盖。则还剩下2*(n-2)的大矩形需要覆盖，即有F(n-2)中方法
 *
 *
 * 由以上两种情况可知，F(n) = F(n - 1) + F(n - 2)，我们只需要知道F(0)，F(1)，就可以求得F(n)。很明显这是一个斐波那契数列的定义。对于斐波那契数列的多种求解方法可以参考【剑指Offer】斐波那契数列
 * 当n = 0的时候，显然有0中覆盖方法，即F(0) = 0
 * 当n = 1的时候，只有一种覆盖方法，即F(1) = 1
 */
public class 矩形覆盖 {
    public int RectCover(int target) {
        if(target <= 0)
            return 0;
        if(target == 1)
            return 1;
        if(target == 2)
            return 2;
        return RectCover(target-1) + RectCover(target-2);
    }
}